package by2019;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * 解决N皇后问题，第二次编写，具体题目参照“N皇后问题”
 * @author carry me home
 *  @version 2.0
 */
public class N皇后问题_V2 {
	
	List<List<String>> reList = new LinkedList<List<String>>() ;

	public static void main(String[] args) {
		 long time = System.currentTimeMillis() ;
		System.out.println(new N皇后问题_V2().solveNQueens(5));
		System.out.println("用时：" + (System.currentTimeMillis() - time));
	}
	/**
	 * 主体函数，直接返回格式化的结果
	 * 调用递归函数进行递归操作
	 * @param n
	 * @return
	 */
	public List<List<String>> solveNQueens(int n) {
		Set<Integer> lie = new HashSet<Integer>() ;
		Set<Integer> pie = new HashSet<Integer>() ;
		Set<Integer> na = new HashSet<Integer>() ;
		int[] a = new int[n] ;
		
		this.DFS(n, 0, a, lie, pie, na);
		return reList;
    }
	
	/**
	 * 深度优先搜索函数，递归搜索每一层
	 * 将能被皇后攻击到的位置存入set中
	 * @param n
	 * 	皇后个数
	 * @param x
	 * 	递归的层数
	 * @param a
	 * 	存皇后位置的数组，下标值为层数，元素为列数
	 * @param lie
	 * 	存在了皇后的列
	 * @param pie
	 * 	能够被皇后攻击到的正斜
	 * @param na
	 * 	能够被皇后攻击到的反斜
	 */
	public  void DFS(int n, int x, int[] a, Set<Integer> lie, Set<Integer> pie, Set<Integer> na) {
		if(x>=n) {
			reList.add(addQ(a)) ;
			return ;
		}
		
		for(int y = 0; y < n; y++) {
			if(lie.contains(y) || pie.contains(y+x) || na.contains(y-x))
				continue ;
			
			lie.add(y) ;
			pie.add(x + y) ;
			na.add(y - x) ;	
			a[x] = y ;
			
			DFS(n, x + 1, a, lie, pie, na);
			
			lie.remove(y) ;
			pie.remove(x + y) ;
			na.remove(y - x) ;
			a[x] = 0 ;
		}
	}
	
	/**
	 * 对皇后的位置进行画图操作
	 * @param b
	 * 	存有皇后位置的数组
	 * @return 
	 * 	返回一种皇后站位的图
	 */
	public List<String> addQ(int[] b) {
		List<String> list = new LinkedList<String>() ;
		StringBuilder sb = new StringBuilder() ;
		
		for(int i = 0; i < b.length; i++) {
			for(int j = 0; j < b.length; j++) {
				if(b[i]==j) {
					sb.append('Q') ;
					continue ;
				}
				sb.append('.') ;
			}
			sb.append(",") ;
		}
		
		list.add(sb.toString()) ;
		return list ;
	}

}
